// 这道题, 应该不难, 我们先计算100以内的所有组合, 由于不存在等边直角三角形, 所以, 最小边为key, 然后可以进行map
// 然后对目标数据进行排序, 重点是使用dfs, 进行深度求索, 到目的地, 把组合数推到result, 最后遍历result, 找到最大值
// 参考答案, 是不停地回溯, 感觉这种, 效率不高, 已经是暴力求解了, 拿到数据, 然后进行盲目的直角三角形验证

//◆尝试两种解法, 第一种是咱的dfs,
//第二种是暴力算法, 试试他们的时间差距
//1
//6 3 4 5 3 4 5
const readline = require("readline");
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
let n;
let initArr = [];
let kinds; // 100以内的直角三角形
rl.on("line", (line) => {
    if (n === undefined) {
        n = Number(line.trim())
        kinds = getKinds()
    } else {
        initArr.push(line.trim().split(" ").map(Number))
        if (initArr.length === n) {
            console.time("a")
            initArr.forEach(arr => console.log(getResult(arr.shift(), arr, kinds)))

            // clear
            n = undefined;
            kinds.length = 0;
            console.timeEnd("a")
        }
    }

})

/**
 *
 * @param n {number} n个数字
 * @param arr {[number]} 数据源
 * @param kinds {{}} 数据源
 * @return {number} 返回最多的组合数
 */
function getResult(n, arr, kinds) {
    //sort
    arr.sort((a, b) => a - b)

    const result = []

    // dfs
    dfs(0, arr, 0, result, kinds)
    return(Math.max(...result))

}

// 100 内的所有组合
function getKinds() {
    let obj = {}
    for (let i = 1; i <= 98; i++) {
        for (let j = i; j <= 99; j++) {
            let k = Math.sqrt(i * i + j * j)
            if (Number.isInteger(k) && k <= 100) {
                if (!obj[i]) {
                    obj[i] = []
                }
                obj[i].push([j, k])
            }
        }
    }
    return obj
}

function dfs(start, arr, count, result, kinds) {
    // 截止
    if (arr.length < 3) {
        result.push(count)
        return
    }

    for (let i = start; i < arr.length; i++) {
        if (kinds.hasOwnProperty(arr[i])) {
            for (const ele of kinds[arr[i]]) {
                [a, b] = ele
                let indexA = arr.slice(i + 1).indexOf(a)
                let indexB = arr.slice(i + 1).indexOf(b)
                if (indexA !== -1 && indexB !== -1) {
                    dfs(0,
                        arr.slice(i + 1, indexA + 1).concat(arr.slice(indexA + 2, indexB + 1)).concat(arr.slice(indexB + 2)),
                        count + 1,
                        result,
                        kinds
                    )
                }
            }
        }
    }
}

